#include <stdio.h>

void merge(int *arr, int l, int m, int r) 
{
    int n1 = l;
    int i = 0;
    int n2 = m +1;
    int tmp[r-l+1];
    while (n1 <= m && n2 <= r) {
        if (arr[n1] < arr[n2]) {
            tmp[i++] = arr[n1++];
        } else {
            tmp[i++] = arr[n2++];
        }
    }
    
    while (n1 <= m) {
        tmp[i++] = arr[n1++];
    } 
    while (n2 <= r) {
        tmp[i++] = arr[n2++];
    }
    i = 0;
    while (i < r-l+1) {
        arr[l++] = tmp[i++];
    }
}

void mergeSort(int *arr, int left, int right) 
{
    if (left < right) {
        int mid = (left + right)/2;
        mergeSort(arr, left, mid);
        mergeSort(arr, mid+1, right);
        merge(arr, left, mid, right);
    }
}


int main(void) 
{
    int arr[10] = {10, 9, 8, 7, 6, 5, 4, 3, 2, 1};
    mergeSort(arr, 0, 9);
    for (int i = 0; i < 10; i++) {
        printf("%d ", arr[i]);
    }

    return 0;
}